package com.some;

import com.review.backpack_01.BP04;

public class BP04_test {
    /*
    混合背包
    p=−1  表示第 i 种物品只能用1次；
    p=0 表示第 i 种物品可以用无限次；
    p>0 表示第 i 种物品可以使用 p 次；
     */
    public static int knapsackProblem(int[] w, int[] v, int[] p, int cap) {
        int[] dp = new int[cap + 1];

        for (int i = 0; i < w.length; i++) {

            if (p[i] == -1) {
                // 01背包
                for (int j = cap; j >= w[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                }
            } else if (p[i] == 0) {
                // 完全背包
                for (int j = w[i]; j <= cap; j++) {
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                }
            } else {
                // 多重背包
                for (int j = cap; j >= w[i]; j--) {
                    for (int k = 0; (k <= p[i]) && (k * w[i] <= j); k++) {
                        dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);
                    }
                }
            }
        }
        return dp[cap];
    }

    public static void main(String[] args) {
        System.out.println(
                knapsackProblem(
                        new int[]{2, 3, 4, 5, 6, 7, 8},
                        new int[]{3, 4, 5, 6, 7, 8, 9},
                        new int[]{1, 1, 0, 0, 1, 3, 4}, 27
                )
        );
        System.out.println(
                knapsackProblem(
                        new int[]{1, 2, 3, 4},
                        new int[]{2, 4, 4, 5},
                        new int[]{-1, 1, 0, 2}, 5
                )
        );

    }
}
